#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int Edge[55][55];
int path[55];
vector<int> G[55];
bool in_[55];
int dis[55];
void SPFA() {
    memset(path, -1, sizeof(path));
    memset(in_, 0, sizeof(in_));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q;
    q.push(0);
    dis[0]=0;
    path[0]=0;
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        in_[now]=false;
        int len=G[now].size();
        int nex;
        for (int i=0; i<len; ++i) {
            nex=G[now][i];
            if (nex==now) continue;
            if (dis[now] + Edge[now][nex] < dis[nex]) {
                dis[nex] = dis[now] + Edge[now][nex];
                path[nex] = now;
                if (!in_[nex]) {
                    in_[nex]=true;
                    q.push(nex);
                }
            }
        }
    }
}
char s[55][55];
int main() {
    int T;
    int n;
    cin>>T;
    while (T--) {
        cin>>n;
        for (int i=0; i<n; ++i) {
            G[i].clear();
        }
        for (int i=0; i<n; ++i) {
            scanf("%s", s[i]);
        }
        for (int i=0; i<n; ++i) {
            int st=0;
            for (int j=0; j<n; ++j) {
                if (s[i][j]=='Y') {
                    Edge[i][j]=st;
                    G[i].push_back(j);
                    ++st;
                }
            }
        }
/*        cout<<"Graph:"<<endl;
        for (int i=0; i<n; ++i) {
            int len=G[i].size();
            cout<<"len: "<<len<<endl;
            for (int j=0; j<len; ++j) cout<<G[i][j]<<' ';
            cout<<endl;
        }
        cout<<endl; */
        SPFA();
        if (path[n-1]==-1) printf("-1\n");
        else {
            int res=0;
            int st=n-1;
            while (path[st]!=st) {
                res+=Edge[path[st]][st];
                st=path[st];
            }
            printf("%d\n", res);
        }
    }
    return 0;
}
